The present invention is directed to a process and apparatus for assigning N objects to M points of a rectangle, where M≧N. The invention is particularly useful in placement of cells in an integrated circuit (IC) chip, although it is also useful in other environments where a large number of object must be placed in a space.
Consider a rectangle having left and right edges a and b, where a<b, and bottom and top edges c and d, where c<d. The rectangle containing a point having coordinates (x,y) can be defined as R={(x,y)|a≦x≦b, c≦y≦d}.
Points P1(x1,y1), P2(x2,y2), . . . , PM(xM,yM), are the points of rectangle R. Objects Q1(x′1,y′1), Q2(x′2,y′2), . . . , QN(x′N,y′N) are the objects to be placed in rectangle R. T is a set of types of points and objects. ti is a type of a point Pi, where i is each member of the sequence of 1 to M (i={overscore (1,M)}). Thus, tiεT. t′i is a type of an object Qi, i={overscore (1,N)}, thus t′iεT. For any pair of types, u ε T and v ε T, the relation of these types TR(u,v) is such that if the object having a type v is allowed to be assigned to a point of type u, TR(u,v)=1. Otherwise, TR(u,v)=0. TR(u,u)=1 for each type u ε T.
The goal of objects assignment is to assign all objects Qi, i={overscore (1,N)} to points Ps(i) (or to find the assignment s(i) for each i={overscore (1,N)}), so that:                a) s(i1)≠s (i2) for any 1≦i1<i2≦N,        b) TR(ts(i),t′i)=1 for any i={overscore (1,N)}, and        c) distances between objects Qi and points Ps(i) is as small as possible.        
The cost C(i,j) of assignment of an object Qi to a point Pj is denoted as follows:
      C    ⁡          (              i        ,        j            )        =      {                                                                      (                                                      x                    j                                    -                                      x                    i                    ′                                                  )                            2                        +                                          (                                                      y                    j                                    -                                      y                    i                    ′                                                  )                            2                                                                          if              ⁢                                                          ⁢                              TR                ⁡                                  (                                                            t                      j                                        ,                                          t                      i                      ′                                                        )                                                      =            1                                                ∞                                                    if              ⁢                                                          ⁢                              TR                ⁡                                  (                                                            t                      j                                        ,                                          t                      i                      ′                                                        )                                                      =            0.                              
One well-known technique of assigning objects is Kuhn's algorithm, which finds the optimal solution s(i) such that the sum
      ∑          i      =      1        N    ⁢          ⁢      C    ⁡          (              i        ,                  s          ⁡                      (            i            )                              )      is the smallest possible value. However, Kuhn's algorithm requires a considerable amount of time to execute. More particularly, execution of Kuhn's algorithm requires time defined as O(N2M2). In practice, cell placement might require processing cell assignments for large values of parameters N and M (N,M>1000), and might be repeated many times during the design process. Consequently, execution of Kuhn's algorithm requires an unacceptable amount of time. Therefore, a need exists for a technique to quickly estimate objects assignment.